package hihocode;

import java.util.Random;


//此题非hihocoder的题目
public class GetMaxAndValue {

	public static void main(String[] args) {
		Random random = new Random();
		int length = random.nextInt(100);
		int[] arr = new int[length];
		for (int i = 0; i < length; i++) {
			arr[i] = random.nextInt(10000);
		}
		int testCase = 100;
		GetMaxAndValue object = new GetMaxAndValue();
		for (int i = 0; i < testCase; i++) {
			int realValue = object.getMaxAndValue(arr);
			int testValue = object.getMaxAndValue2(arr);
			if(realValue != testValue){
				for (int j = 0; j < arr.length; j++) {
					System.out.print(arr[i] + " ");
				}
				System.out.println();
			}
		}
	}
	
	public int getMaxAndValue(int[] arr){
		int max = 0;
		int res = 1;
		
		for (int i = 0; i < arr.length; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				res = arr[i] & arr[j];
				if(res > max){
					max = res;
				}
			}
		}
		return max;
	}
	
	private class TrieNode {
		// path表示有多少个数共用这个结点
		public int path;
		public TrieNode[] child;

		// 只有0,1
		public TrieNode() {
			path = 0;
			// 这里假定只包含26个字母的
			child = new TrieNode[2];
		}
	}

	public void add(int x, TrieNode root) {
		for (int i = 31; i >= 0; i--) {
			int bit = (x >> i) & 1;
			if (root.child[bit] == null) {
				root.child[bit] = new TrieNode();
			}
			root = root.child[bit];
			root.path++;
		}
	}

	public int search(int x, TrieNode root) {
		int ans = 0;
		for (int i = 31; i >= 0; i--) {
			int bit = (x >> i) & 1;
			ans = ans << 1;
			// root.path > 1表示的是最少有两个数公用该结点
			//但是这个策略是错的...
			//比如10101
			//01100
			//00101
			//当x的bit为1的时候，我们自然想到的是要去找1
			//但是若是0的时候，我们无法知道下一个该查找的是0还是1啊
			if (root.child[1] != null && root.path > 1) {
				ans += bit;
				root = root.child[bit];
			} else {
				root = root.child[0];
			}
		}
		return ans;
	}
	
	public int getMaxAndValue2(int[] arr){
		int ans = 0;
		TrieNode root = new TrieNode();
		for(int i = 0; i < arr.length; i++){   
			add(arr[i], root);
		}
		for(int i = 0; i < arr.length; i++){   
	        ans =  Math.max(ans, search(arr[i], root));  
		}
		return ans;
	}
}
